摘要 :
Let P be a set of n points in ℝ3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n-7 different directions if n is even and at least 2n-5 if n is odd. T...
展开
Let P be a set of n points in ℝ3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n-7 different directions if n is even and at least 2n-5 if n is odd. The bound for odd n is sharp.
收起
摘要 :
Let P be a set of n points in ℝ3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n-7 different directions if n is even and at least 2n-5 if n is odd. T...
展开
Let P be a set of n points in ℝ3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n-7 different directions if n is even and at least 2n-5 if n is odd. The bound for odd n is sharp.
收起
摘要 :
(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals3 that have at most c distinct orientations, is O(c4n2+ε), for any ε>0. This result is a step towards proving the long-sta...
展开
(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals3 that have at most c distinct orientations, is O(c4n2+ε), for any ε>0. This result is a step towards proving the long-standing conjecture that the Euclidean Voronoi diagram of lines in three dimensions has near-quadratic complexity. It provides the first natural instance in which this conjecture is shown to hold. In a broader context, our result adds a natural instance to the (rather small) pool of instances of general 3-dimensional Voronoi diagrams for which near-quadratic complexity bounds are known.
收起
摘要 :
(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals3 that have at most c distinct orientations, is O(c4n2+ε), for any ε>0. This result is a step towards proving the long-sta...
展开
(MATH) We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in $\reals3 that have at most c distinct orientations, is O(c4n2+ε), for any ε>0. This result is a step towards proving the long-standing conjecture that the Euclidean Voronoi diagram of lines in three dimensions has near-quadratic complexity. It provides the first natural instance in which this conjecture is shown to hold. In a broader context, our result adds a natural instance to the (rather small) pool of instances of general 3-dimensional Voronoi diagrams for which near-quadratic complexity bounds are known.
收起
摘要 :
We show that that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n2+ε), for an...
展开
We show that that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n2+ε), for any ε>0. We also show that when the sites are n segments in 3-space, this complexity is O(n2 α(n) log n). This generalizes previous results by Chew et al. [9] and by Aronov and Sharir [4], and solves an open problem put forward by Agarwal and Sharir [2]. Specific distance functions for which our results hold are the L1 and the L∞ metrics. These results imply that we can preprocess a collection of polyhedra as above into a near-quadratic data structure that can answer Δ-approximate Euclidean nearest-neighbor queries amidst the polyhedra in time O(log (n/Δ)), for an arbitrarily small Δ>0.
收起
摘要 :
We show that that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n2+ε), for an...
展开
We show that that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n2+ε), for any ε>0. We also show that when the sites are n segments in 3-space, this complexity is O(n2 α(n) log n). This generalizes previous results by Chew et al. [9] and by Aronov and Sharir [4], and solves an open problem put forward by Agarwal and Sharir [2]. Specific distance functions for which our results hold are the L1 and the L∞ metrics. These results imply that we can preprocess a collection of polyhedra as above into a near-quadratic data structure that can answer Δ-approximate Euclidean nearest-neighbor queries amidst the polyhedra in time O(log (n/Δ)), for an arbitrarily small Δ>0.
收起
摘要 :
(MATH) Given a set L of n lines in $\reals^3$, let JLdenote the set of all joints of L; joints are points in $\reals^3$ that are incident to at least three non-coplanar lines in L. We show that there are at most O(n5/3) incidenc...
展开
(MATH) Given a set L of n lines in $\reals^3$, let JLdenote the set of all joints of L; joints are points in $\reals^3$ that are incident to at least three non-coplanar lines in L. We show that there are at most O(n5/3) incidences between JLand L.(MATH) This result leads to related questions about incidences between L and a set P of m points in $\reals^3$: First, we associate with every point p ε P the minimum number of planes it takes to cover all lines incident to p. Then the sum of these numbers is at most $$ O(m^4/7n^5/7+m+n) ~. $$ Second, if each line forms a fixed given non-zero angle with the xy-plane---we say the lines are equally inclined--- then the number of (real) incidences is at most $$ O(\min\m^3/4n^1/2\kappa(m),m^4/7n^5/7\ + m + n) ~, $$ where $\kappa(m) = (\log m)^O(\alpha^2(m))$, and $\alpha(m)$ is the slowly growing inverse Ackermann function. These bounds are smaller than the tight Szemeredi-Trotter bound for point-line incidences in $\reals^2$, unless both bounds are linear. They are the first results of that type on incidences between points and 1-dimensional objects in $\reals^3$. This research was stimulated by a question raised by G. Elekes.
收起
摘要 :
(MATH) Given a set L of n lines in $\reals^3$, let JLdenote the set of all joints of L; joints are points in $\reals^3$ that are incident to at least three non-coplanar lines in L. We show that there are at most O(n5/3) incidenc...
展开
(MATH) Given a set L of n lines in $\reals^3$, let JLdenote the set of all joints of L; joints are points in $\reals^3$ that are incident to at least three non-coplanar lines in L. We show that there are at most O(n5/3) incidences between JLand L.(MATH) This result leads to related questions about incidences between L and a set P of m points in $\reals^3$: First, we associate with every point p ε P the minimum number of planes it takes to cover all lines incident to p. Then the sum of these numbers is at most $$ O(m^4/7n^5/7+m+n) ~. $$ Second, if each line forms a fixed given non-zero angle with the xy-plane---we say the lines are equally inclined--- then the number of (real) incidences is at most $$ O(\min\m^3/4n^1/2\kappa(m),m^4/7n^5/7\ + m + n) ~, $$ where $\kappa(m) = (\log m)^O(\alpha^2(m))$, and $\alpha(m)$ is the slowly growing inverse Ackermann function. These bounds are smaller than the tight Szemeredi-Trotter bound for point-line incidences in $\reals^2$, unless both bounds are linear. They are the first results of that type on incidences between points and 1-dimensional objects in $\reals^3$. This research was stimulated by a question raised by G. Elekes.
收起
摘要 :
(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m4/7n17/21+m2/3n2/3+m+n); the bound is optimal for m n3/2. This result extends recent work on point-circle inc...
展开
(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m4/7n17/21+m2/3n2/3+m+n); the bound is optimal for m n3/2. This result extends recent work on point-circle incidences in the plane, but its proof requires a different analysis. The bound improves upon a previous bound, noted by Akutsu et al. [2] and by Agarwal and Sharir [1], but it is not as sharp (when m is small) as the recent planar bound of Aronov and Sharir [3]. Our analysis extends to yield the same bound (a) on the number of incidences between m points and n circles in any dimension d&rhoe; 3, and (b) on the number of incidences between m points and n arbitrary convex plane curves in $\reals^d$, for any d&rhoe; 3, provided that no two curves are coplanar. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space, and were already used to obtain a lower bound for the number of distinct distances in a set of n points in 3-space.
收起
摘要 :
(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m4/7n17/21+m2/3n2/3+m+n); the bound is optimal for m n3/2. This result extends recent work on point-circle inc...
展开
(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m4/7n17/21+m2/3n2/3+m+n); the bound is optimal for m n3/2. This result extends recent work on point-circle incidences in the plane, but its proof requires a different analysis. The bound improves upon a previous bound, noted by Akutsu et al. [2] and by Agarwal and Sharir [1], but it is not as sharp (when m is small) as the recent planar bound of Aronov and Sharir [3]. Our analysis extends to yield the same bound (a) on the number of incidences between m points and n circles in any dimension d&rhoe; 3, and (b) on the number of incidences between m points and n arbitrary convex plane curves in $\reals^d$, for any d&rhoe; 3, provided that no two curves are coplanar. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space, and were already used to obtain a lower bound for the number of distinct distances in a set of n points in 3-space.
收起
原文获取